The present invention relates generally to encoding data and in particular, to a method and apparatus for encoding data utilizing low-density parity-check (LDPC) codes.
An LDPC code is a linear block code specified by a parity-check matrix H. In general, an LDPC code is defined over a Galois Field GF(q), qxe2x89xa72. If q=2, the code is a binary code. As with all linear block codes, a k-bit information block S1xc3x97k is generally encoded by the code generator matrix Gkxc3x97n to become an n-bit codeword X1xc3x97n, and the code rate is r=k/n. The codeword x is transmitted through a noisy channel, and the received signal vector y is passed to the decoder to estimate the information block s1xc3x97k.
Given an n-dimensional space, the rows of G span the k-dimensional codeword subspace C, and the rows of the parity-check matrix Hmxc3x97n span the m-dimensional dual space Cxe2x8axa5, where m=nxe2x88x92k. Since x=sG and GHT=0, it follows that xHT=0 for all codewords in subspace C, where xe2x80x9cTxe2x80x9d denotes matrix transpose. In the discussion of LDPC codes, this is generally written as
HxT=0T, xe2x80x83xe2x80x83(1)
where 0 is a row vector of all zeros, and the codeword xT is:             x      T        =          [                                                  p              1                                                            ⋮                                                              p                              n                -                k                                                                                        s              1                                                            ⋮                                                              s              k                                          ]        ;
where,
p1, . . . pnxe2x88x92k are the parity check bits; and
s1, . . . sk are the systematic bits, equal to the information bits within the information block.
In order to use an LDPC code with good error-correcting performance, an appropriate low-density parity-check matrix H has to be defined. For most irregular LDPC codes, this requires making a large portion of the columns of H to be weight-2 (i.e., two ones in a column) in order to keep the overall density low (i.e., the overall matrix should be sparse). This large number of weight-2 columns can allow high weights (e.g., 30) to be assigned to some columns while still maintaining a low average column weight in H. (Note that the row weights are usually limited in range and are relatively small.)
Designing a parity-check matrix with various row and column weights is complicated when error performance is considered. For example, a matrix can be constructed with a series of randomly generated columns while satisfying the row weight and column weight constraints, however, with a large percentage of weight-2 columns in the matrix, randomly-generated weight-2 columns can easily contain a bad structure which induces an undetectable error event and a low minimum distance. In general, an undetectable error event of Nud bits could happen if Nud columns of the parity-check matrix sum (modulo 2) to the all-zero column. The all-zero column summation occurs with higher frequency when the parity-check matrix has a small size and contains weight-2 columns. The undetectable error event is directly linked to the minimum distance of the code which is equal to min(Nud). As a result, a randomly-generated parity-check matrix can have a small minimum distance, which causes a high probability of undetectable errors and an error floor at high signal-to-noise ratios. Furthermore, since code bits (elements of x) associated with weight-2 columns are much more prone to errors than code bits associated with higher-weight columns, a large percentage of undetectable frame errors is expected to involve weight-2 columns. Although there are several prior-art code construction guidelines cited or implied in literature such as (a) avoiding cycles of length 4 and (b) avoiding overlap between weight-2 columns when possible, these guidelines may not be sufficient for good error performance codes. Therefore, there is a need for deterministic distribution of weight-2 columns in which the occurrence of undetected frame errors is reduced in order to significantly enhance code performance in comparison to a randomly-constructed parity-check matrix.
Notwithstanding the above problem, another issue of LDPC codes is the high encoding complexity of the straightforward method using the generator matrix G corresponding to the H matrix defining the code. For a systematic LDPC encoder, parity check bit pi, i=1, . . . , m, is generally computed from the given information bits, s1, . . . , sk, m=nxe2x88x92k. Letting the codeword be x=[p1, . . . , pm, s1, . . . , sk], the parity check bits satisfy the parity-check equations of (1). A conventional encoding method transforms the parity-check matrix H into a systematic form Hsys=[Imxc3x97m, PT] through Gaussian elimination and column reordering so that the corresponding code generator matrix is G=[Pkxc3x97m, Ikxc3x97k]. Therefore, the conventional encoder calculates the parity check bits using
└p1, . . . , pm┘=└s1, . . . , sk┘P. xe2x80x83xe2x80x83(2):
This straightforward method can cause implementation problems especially when the codeword size n is large. First, although H has low density (i.e., with a few 1""s in the matrix and the number of 1""s per row not growing with n), P and hence G usually have high density (i.e., many 1""s in the matrix and the number of 1""s per row increasing as n increases). Implementing the conventional encoder can require a large amount of memory to store the positions of the 1""s in P. Secondly, due to the high density of P, the number of binary additions (only counting the terms when the elements of P are xe2x80x981xe2x80x99) is on the order of n2; implying that the encoding complexity grows quadratically with n. Therefore, there is a need for an efficient encoder for irregular LDPC codes that takes advantage of the structure of a good performing irregular LDPC code to minimize preprocessing and admit a simple encoding program.